package base.demo;

import base.sort.MergeSort;
import base.utils.PrintUtils;

import java.util.Arrays;

public class MergeSortDemo {

    static int[] array = {4, 2, 5, 3, 1, 6,8,7,0,9};
    static int[] arrayTest = {4, 5, 3, 1, 6, 9};

    public static void main(String[] args) throws Exception {
        MergeSort sort = new MergeSort();
//        arrayTest = sort.sort(arrayTest);
        sort.mergeSort(array);
        PrintUtils.print(array);
    }


    public static int[] sortDemo01(int[] sourceArray) {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        if (arr.length < 2) return arr;

        int middle = (int) Math.floor(arr.length / 2);
        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return mergeDemo1(sortDemo01(left), sortDemo01(right));
    }

    private static int[] mergeDemo1(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

    public void megerSort01(int[] arr, int[] result, int start, int end) {
        if (start > end) return;

        int len = end - start, mid = (len / 2) + start;

        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;

        megerSort01(arr, result, start1, end1);
        megerSort01(arr, result, start2, end2);

        int k = start;
        while (start1 <= end1 && start2 <= end2) {
            result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
        }

        while (start1 <= end1) result[k++] = arr[start1++];
        while (start2 < end2) result[k++] = arr[start2++];

        for (k = start; k <= end; k++) arr[k] = result[k];
    }


    public void megerSort02(int[] arr, int[] result, int start, int end) {
        if (start > end) return;


        int len = end - start, mid = (len / 2) + start;
        int leftStart = start, leftEnd = mid;
        int rightStart = mid + 1, rightEnd = end;

        megerSort02(arr, result, leftStart, leftEnd);
        megerSort02(arr, result, rightStart, rightEnd);

        int k = start;

        while (leftStart <= leftEnd && rightStart <= rightEnd)
            result[k++] = arr[leftStart] < arr[rightStart]
                    ? arr[leftStart++] : arr[rightStart++];


        while (leftStart <= leftEnd) result[k++] = arr[leftStart++];

        while (rightStart < rightEnd) result[k++] = arr[rightStart++];


        for (k = start; k < end; k++) arr[k] = result[k];

    }


}








































